package offer;

/**
 * @author zhanb
 * @Date 2020/5/20
 */
public class Solution4 {

    public static void main(String[] args) {
        int mx[][] = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };

/*        *for (int [] row : mx){
            for (int item : row){
                System.out.print(item+"\t");
            }
            System.out.println();
        }*/

        System.out.println(findNumberIn2DArray3(mx, 5));


    }


    /**
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，
     * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
     * matrix
     * [
     * [1,   4,  7, 11, 15],
     * [2,   5,  8, 12, 19],
     * [3,   6,  9, 16, 22],
     * [10, 13, 14, 17, 24],
     * [18, 21, 23, 26, 30]
     * ]
     * 给定 target = 5，返回 true。
     * <p>
     * 给定 target = 20，返回 false。
     *
     * @param matrix
     * @param target
     * @return 暴力匹配
     */
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int item : row) {
                if (item == target) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 优化
     * 标志数性质： 将 matrix 中的左下角元素（标志数）记作 flag ，则有:
     * <p>
     * 若 flag > target ，则 target 一定在 flag 所在行的上方，即 flag 所在行可被消去。
     * 若 flag < target ，则 target 一定在 flag 所在列的右方，即 flag 所在列可被消去。
     * <p>
     * 本题解以左下角元素为例，同理，右上角元素 也具有行（列）消去的性质。
     * <p>
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 根据以上性质，设计算法在每轮对比时消去一行（列）元素，以降低时间复杂度。
     * 从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比：
     * 当 matrix[i][j] > target 时： 行索引向上移动一格（即 i--），即消去矩阵第 i 行元素；
     * 当 matrix[i][j] < target 时： 列索引向右移动一格（即 j++），即消去矩阵第 j 列元素；
     * 当 matrix[i][j] == target 时： 返回 truetrue 。
     * <p>
     * <p>
     * 若行索引或列索引越界，则代表矩阵中无目标值，返回 falsefalse 。
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) {
                i--;
            } else if (matrix[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 右上角标志位解法
     * @param matrix
     * @param target
     * @return
     */
    public static boolean findNumberIn2DArray3(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length-1;
        while (i < matrix.length && j>=0) {
            if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}

